\chapter{Dolovanie dát a procesov}
\label{chap:dolovanie}

V predchádzajúcej kapitole sme sa zoznámili so znalostnými systémami, ktoré
sme nazvali analytické, pretože sú schopné manipulácie so symbolmi a
inferencie, čo v konečnom dôsledku umožňuje analyzovať, interpretovať a
využiť symbolovo reprezentované poznatky uložené v CDSS systémoch. V CDSS
systémoch ale často musíme spracovávať aj dáta, ktoré nemožno symbolovo
reprezentovať vôbec, prípadne iba veľmi ťažko, a so stratou. Medzi takéto
typy dát v súčasnosti radíme neštruktúrované zdravotné záznamy vo forme
,,surového'' textu. Môže ísť napríklad o staršiu dokumentáciu, ktorá je
dnes spätne digitalizovaná. Ale tiež sem radíme fotografické, či RTG
snímky, senzorové dáta, a tak ďalej, z ktorých pri vhodnom spracovaní môže
CDSS systém čerpať užitočné informácie pre potrebu podpory rozhodovania.

Nachádzaním súvislostí, príznakov, vzorov, či skrytého významu v takýchto
dátach sa zaoberá práve oblasť dolovania dát a znalostí, ktorá pre tieto
úlohy využíva predominantne metódy strojového učenia.

		\subsubsection{Čo sú a na riešenie akých problémov sa používajú metódy strojového učenia}
			
			S nástupom a prudkým vývojom výpočtových a informačných technológií sa výrazne zväčšuje aj objem 
			dát, ktoré vznikajú ich používaním. Neformálny popis tohoto trendu sa podobá na Moorov zákon, založený na pozorovaní 
			vývoja množstva komponentov na integrovanom obvode: približne každé dva roky sa ich počet na integrovanom 
			obvode zdvojnásobí \cite{moore}. Toto tvrdenie bolo vyslovené v roku 1965 Gordonom Moorom a jeho platnosť bola odhadnutá na 
			niekoľko rokov dopredu. Aj po skoro pol storočí sa tento odhad javí ako stále platný, očakáva sa však, že sa rýchlosť vývoja 
			začne v blízkej dobe spomaľovať, keď narazí na niektorú z fyzikálnych bariér. 
			
			Podobne ako Moorov zákon hovorí o zvyšovaní výkonu výpočtových technológií, zväčšuje sa aj úložná kapacita zariadení, medzi rokmi
			1986 a 2007 sa priemerná úložná kapacita na osobu zdvojnásobila približne každé 3 roky \cite{hilbert-data}.
			
			Odhad množstva všetkých človekom vytvorených a replikovaných dát na svete z roku 2011 je $1,8$ zettabajtu ($10^{21}$ bajtov) \cite{idc-data}. 
			Odhad množstva všetkých uložených dát (na rôznych dátových nosičoch, optimálne komprimovaných) z roku 2007 je $295$ exabajtov 
			($10^{18}$ bajtov) \cite{hilbert-data}.

			Pre ilustráciu, Veľký hadrónový urýchľovač (LHC - Large hadron collider) v CERN-e dokáže pri prebiehajúcom experimente 
			vygenerovať približne petabajt hrubých dát za sekundu ($10^{15}$ bajtov). Také množstvo dát sa nedá jednoducho uložiť a spracovať neskôr,
			preto je potrebné dáta ihneď filtrovať a ponechávať iba tie, ktoré sú potenciálne zaujímavé pre vedcov. Ročne je takto uložených približne 
			25 petabajtov dát \cite{cern-storage}. 

			Čím viac dát vieme získať, či už ide o dáta experimentálne, štatistické, medicínske, ekonomické alebo iné, tým menej sú
			pre ľudského pozorovateľa prehľadné a tým menej relevantných informácií a záverov vieme z dát odvodiť. Na riešenie tohoto
			problému sa preto používajú metódy strojového učenia. 

			Na odhalenie vzorov alebo skrytej štruktúry v dátach slúžia metódy učenia bez učiteľa (\emph{unsupervised learning}), na modelovanie 
			vstupných dát za účelom predpovedania výstupných dát resp. na abstrahovanie modelu dát do podoby funkcie vstupov a výstupov 
			sa používa učenie s učiteľom (\emph{supervised learning}). Osobitnou kategóriou je učenie posilňovaním (\emph{reinforcement learning)} ktoré je 
			založené na behaviorálnej psychológií - algoritmus sa snaží naučiť optimálne správanie (v dlhodobom horizonte maximalizovať zisk) 
			v stavovom priestore na základe senzorických vstupov a signálu odmeny pre každý stav. %\cite{aima:2003} \cite{patt-rec}

		\subsubsection{Príklady použitia metód strojového učenia}
			
			So strojovým učením sa pravdepodobne stretávame denne a vôbec o tom nemusíme vedieť. 

			Jedným z typických príkladov použitia strojového učenia je automatická detekcia a filtrácia emailového spamu, teda nevyžiadanej elektronickej pošty. 
			Na základe vzorovej (\emph{trénovacej}) množiny emailov, kde je okrem obsahu správy uvedená ešte aj informácia o tom, do ktorej kategórie daný mail 
			patrí (napr. pošta / spam), vieme počítač naučiť triediť prichádzajúce správy do kategórií \cite{stat-learn}. 

			Je dobré si všimnúť, že trénovacia množina, na ktorej budeme algoritmus spúšťať a na ktorej si bude postupne upravovať vnútorné parametre 
			(teda učiť sa) obsahuje už aj výsledky, ktoré by sme očakávali ku každému mailu. Preto sa použitá metóda volá \emph{učenie s učiteľom}, pretože program 
			dostáva úplnú informáciu o dátach a nakoniec pri trénovaní zistí či odpovedal správne alebo nie - s touto informáciou sa vie prispôsobiť tak, 
			aby nabudúce neurobil chybu. Tento príklad je ukážkou \emph{klasifikačnej} úlohy - triedime vstupné dáta do kategórií (tried). 

			Iným príkladom je situácia, kedy sa snažíme odhadnúť napríklad cenu nehnuteľnosti na základe jej parametrov (napr. rozloha, vzdialenosť od centra apod.)
			Pri trénovaní opäť použijeme trénovaciu množinu, tentokrát však očakávanou hodnotou každého príkladu z množiny nebude kategória, ale číselná hodnota 
			(v tomto príklade to môže byť cena, za ktorú sa daný dom v skutočnosti predal). Na takýto problém použijeme inú metódu učenia s učiteľom - \emph{regresiu}.

			V iných prípadoch však nie je cieľom naučiť model ako súvisia vstupné a výstupné dáta (alebo nie je možné použiť učenie s učiteľom, napríklad preto, že cieľová
			hodnota sa nedá jednoducho získať) a zaujíma nás štruktúra dát, skryté vzory v dátach. Tu nastupujú metódy \emph{učenia bez učiteľa}, príkladom ktorých sú napr. 
			\emph{zhlukovanie (clustering)}, \emph{redukcia dimenzionality} alebo \emph{samo-organizujúce sa mapy (SOM - self-organizing maps)}.
 
			Zhlukovanie sa používa napríklad pri aplikáciach počítačového videnia na segmentovanie obrazu, redukcia dimenzionality dát a samo-organizujúce sa mapy 
			zase pri vizualizácií vysoko-rozmerných dát.


 	 \section{Základné paradigmy strojového učenia}
  
		\subsection{Učenie s učiteľom (supervised learning)}
			Učenie s učiteľom je jedným z fundamentálnych prístupov strojového učenia. Základným princípom je trénovanie štatistického modelu pomocou 
			pripravenej množiny dát, ktorá sa zvykne nazývať \emph{trénovacou množinou}. Model má niekoľko vstupných premenných (v príklade s cenou nehnuteľnosti 
			môžeme identifikovať napríklad rozlohu a vzdialenosť  od centra mesta) a jednu alebo viac výstupných. Vstupy aj výstupy sú spravidla z rovnakého univerza 
			(napríklad reálne čísla). 

			Trénovacia množina obsahuje príklady vstupných hodnôt, ku ktorým je priradená očakávaná výstupná hodnota. Model sa najprv natrénuje na trénovacej množine 
			dát, aby potom mohol na základe skutočných vstupov predpovedať výstupnú hodnotu.  Tieto vstupné dáta už samozrejme neobsahujú cieľovú výstupnú hodnotu - 
			tú chceme aby nám vypočítal naučený program. Podľa typu výstupnej hodnoty odlišujeme v učení s učiteľom regresiu a klasifikáciu. Regresia má kvantitatívny 
			výstup (cena nehnuteľnosti v úvodnom príklade), zatiaľ čo klasifikácia má výstup kvalitatívny (pošta / spam v úvodnom príklade) reprezentovaný numericky 
			\cite{stat-learn}. 

			Po natrénovaní modelu obvykle nasleduje testovanie - chceme si byť istí, že sa model naučil požadovaný vzor z trénovacích dát. Vytvoríme si preto testovaciu 
			množinu, ktorá sa obvykle oddelí od trénovacej na začiatku trénovania. Je dôležité, aby testovacie príklady boli pre model úplne nové, inak nedostaneme 
			objektívne zhodnotenie nášho modelu (ak by sme ho testovali na trénovacích dátach, výsledky budú veľmi dobré - pretože počas trénovania sa menia vnútorné 
			parametre modelu práve tak, aby bola chyba na trénovacej množine čo najmenšia). Nás však pri testovaní modelu zaujíma, ako dobre bude fungovať na dátach, 
			ktoré ešte nevidel ale ktoré sledujú rovnaký vzor ako tie, na ktorých bol model trénovaný (teda ako dobre dokáže náš model \emph{generalizovať}). Ak sme s testovacou 
			chybou modelu spokojní, natrénovaný model si ponecháme alebo celý proces opakujeme s novými parametrami (iná trénovacia množina, iné parametre učenia).
			
			Nakoniec, keď je náš model natrénovaný aj otestovaný, chceme ho použiť na účel pre ktorý bol vytvorený. Tu už stačí dať modelu na vstup namerané dáta a nechať
			ho vypočítať (rovnako ako pri trénovaní, tentoraz ale už model neupravujeme - neučíme) výstupnú hodnotu, ktorú použijeme.
			
			Pre lepšiu predstavu, ako takýto štatistický model v skutočnosti vyzerá a pracuje popíšeme jeden základný model použiteľný pre regresné aj klasifikačné
			problémy, lineárny model najmenších štvorcov (Least-squares linear model) \cite{stat-learn}. 
			
			\subsubsection{Regresia}
				Nech náš model má na vstupe vektor vstupných hodnôt dĺžky $n$ z oboru reálnych čísel, ktorý označíme $X$, $X \in \mathbb{R}^{n}$ a $x_i$
				sú jednotlivé indexované zložky vektora vstupných hodnôt (nazývané aj ako atribúty, črty, resp. \emph{features}) počnúc indexom $1$, $X=(x_{1}, x_{2},\ldots,x_{n})$ .
				
				Nech $Y$ je výstupná premenná (cieľová premenná, \emph{target}) pre vstupný vektor $X$, $Y \in \mathbb{R}$ a nech $\Theta = (\theta_{0}, \theta_{1}\ldots,\theta_n)$ 
				je vektor parametrov modelu. Je dobré si všimnúť, že vektor $X$ je $n$-rozmerný, zatiaľ čo vektor parametrov $\Theta$ je $(n+1)$-rozmerný. Na vypočítanie 
				\emph{predpovedanej} výstupnej hodnoty $\hat{Y}$ použijeme následovnú rovnicu: 
				\begin{displaymath}
					\hat{Y}= \theta_{0} + \theta_{1}x_{1} + \theta_{2}x_{2} + \ldots + \theta_{n}x_{n}
				\end{displaymath}
				To sa dá zapísať ako
				\begin{displaymath}
					\hat{Y}=\theta_0+\sum_{i=1}^n x_i\theta_i
				\end{displaymath}
				
				$\theta_0$, nazývané aj ako výchylka (\emph{bias}) má špeciálny význam, ktorý sa dá ilustrovať na príklade jednorozmerných vstupných dát (máme teda len \emph{jeden vstup} 
				a jeden výstup). V takom prípade máme rovnicu pre predikciu výstupu: 
				\begin{displaymath}
					\hat{Y}=\theta_0+\theta_1x_1
				\end{displaymath}
				čo je vlastne rovnica priamky a $\theta_0$ je posun priamky v smere $y$-ovej osy. Keď túto interpretáciu rozšírime do $(n + 1)$-rozmerného priestoru dát ($n$ 
				rozmerné dáta a výstupná hodnota), rovnica pre $\hat{Y}$ je rovnica nadroviny v danom $(n+1)$-rozmernom priestore. Ak ku prvkom vstupného vektora $X$ 
				pridáme konštantu $x_0=1$, nadrovina bude obsahovať počiatok a stane sa podpriestorom, ak nie, bude len afinnou množinou pretínajúcou $y$-ovú os v bode 
				$(0, \theta_0)$ \cite{stat-learn}. V ďaľšom teda bude $x_0=1$ súčasťou vektora vstupov $X$, rovnako ako $\theta_0$ je súčasťou vektora parametrov $\Theta$. Potom 
				môžeme použiť maticový zápis pre výpočet predpovedanej hodnoty 
				\begin{displaymath}
					\hat{Y}=X^T\Theta
				\end{displaymath} 
				pričom všetky vektory sú uvádzané ako stĺpcové, $X^T$ označuje maticovú transpozíciu. Ukázali sme, ako pomocou tohoto modelu vypočítať výstupnú hodnotu z 
				vektora vstupov a vektora parametrov. V tomto zápise ide vlastne o skalárny súčin vektora vstupov a vektora parametrov, resp. lineárnu kombináciu vstupov.

				Ostáva už len vypočítať parametre $\Theta$, teda vlastne natrénovať model. Na to budeme potrebovať \emph{trénovaciu množinu dát} a \emph{chybovú funkciu}.
				
				Trénovacia množina dát je tvorená $t$ dvojicami $(X_i, Y_i)$, \newline $i \in \{0, 1, \ldots, (t-1)\}$, ktoré predstavujú vektory vstupných hodnôt $X_i$ popisujúce jav, 
				ktorý chceme modelovať, aj s ich výstupnými hodnotami $Y_i$. 

				Štatistický model, ktorý na týchto dátach natrénujeme, bude odrážať súvislosti vstupov a výstupov práve týchto dát, preto je vhodný výber trénovacej množiny 
				veľmi dôležitý. Ak model natrénujeme na dátach, ktoré nereprezentujú jav, ktorý chceme modelovať, nebude model počítať to, čo očakávame. 

				Pre testovaciu množinu platí to isté, avšak jej úloha je odlišná. Ako už bolo spomenuté, testovacie dáta obvykle získame tak, že z trénovacích dát malú 
				časť odoberieme a ďalej nepoužijeme pri trénovaní. Tu je potrebné dať si pozor na to, aká je štruktúra trénovacích dát a či odoberáme reprezentatívnu vzorku
				(môže sa stať, že trénovacie dáta sú napríklad zoradené alebo zoskupené podľa niektorého atribútu, čo nie je dobrá štruktúra trénovacej množiny).
				Dobrým zvykom teda je trénovacie dáta pred manipuláciou premiešať, a až potom rozdeliť na testovacie a trénovacie. 
				
				Je potrebné dodať, že medzi takéto dobré zvyky patrí aj tzv. \emph{normalizácia} dát. Jednotlivé atribúty vstupných dát totiž nemusia mať rovnakú 
				mierku - napr. zatiaľ čo jeden atribút dosahuje hodnoty rádovo v desiatkách, druhý môže dosahovať hodnoty v miliónoch a jeho numerický prínos vo 
				výsledku tak bude rádovo väčší ako prínos prvého atribútu, zatieni jeho význam. To je ale situácia, ktorá je potenciálne nežiadúca - naším cieľom môže byť stav, 
				kedy všetky atribúty modelu prezentujeme ako rovnocenné, a rozhodnutie, ktorý atribút má aký prínos pre výsledok (vlastne naše hľadané parametre 
				$\theta_i$) necháme na náš model. Vstupné dáta (nie len trénovacie, ale všetky, aj tie, na ktorých budeme model skutočne používať) 
				teda musíme upraviť tak, aby mali všetky atribúty rovnakú mierku - napríklad tak, že ich preškálujeme do intervalu $0\ldots1$. 
				
				Je dôležité si uvedomiť, že pri normalizácií resp. škálovaní dát vždy použijeme rovnaké škálovacie parametre - tie, ktoré sme vypočítali pre trénovaciu množinu. 
				Ak normalizujeme trénovacie dáta, musíme pre správne fungovanie modelu preškálovať rovnakými koeficientami aj všetky ďalšie vstupné dáta modelu.
				
				Avšak späť ku trénovaniu lineárneho modelu pre regresiu. Ako poslednú potrebujeme definovať chybovú funkciu. Tou bude funkcia pre výpočet najmenších 
				štvorcov (\emph{least-squares}):
				\begin{displaymath}
					Err(\Theta) = \sum_{i=0}^{(t-1)} (Y_i -\hat{Y}_i )^2
				\end{displaymath}
				Ide teda o sumu cez všetky trénovacie príklady, kde počítame štvorec rozdielu skutočnej výstupnej hodnoty a modelom vypočítanej výstupnej hodnoty, pre každý 
				trénovací príklad. Táto funkcia nám hovorí, ako ďaleko je náš momentálny model (jeho výstupné hodnoty cez všetky trénovacie dáta) ku skutočným výsledkom
				trénovacej množiny (učiteľský signál). Tu sa dostávame ku kľúčovej časti - náš model budeme považovať za dobre naučený, keď chybová funkcia pre jeho výstupy bude
				produkovať minimálny výsledok, z čoho odvodíme, že náš model vie vypočítať výstupné hodnoty pre jednotlivé trénovacie príklady s najmenšou možnou chybou
				od očakávaných hodnôt. 

				Ako vypočítať výstupnú hodnotu $\hat{Y}$ sme už ukázali, takže chybovú funkciu môžeme prepísať do tvaru
				\begin{displaymath}
					Err(\Theta) = \sum_{i=0}^{(t-1)} (Y_i - X_{i}^T\Theta )^2
				\end{displaymath}
				Cieľom trénovania je nájsť parametre $\Theta$, ktoré minimalizujú túto funkciu. Rovnica pre výpočet parametrov, ktoré ju minimalizujú, je v maticovom
				zápise vyjadrená následovne
				\begin{displaymath}
					\Theta = (X^{T}X)^{-1}X^{T}Y
				\end{displaymath}
				a jej odvodenie je popísané napríklad v \cite{stat-learn}, \cite{patt-rec}. V tejto rovnici reprezentuje $X$ maticu, ktorej každý riadok obsahuje
				vstupné hodnoty jedného vstupného dátového príkladu. $X$ má teda $t$ riadkov a $n+1$ stĺpcov. $Y$ je vektor výstupných hodnôt trénovacích
				príkladov dĺžky $t$.
				
				Pre doplnenie, pre lineárny model regresie je možné použiť aj iné chybové funkcie, napríklad  
				\begin{displaymath}
					\sum_{i=0}^{(t-1)} \lvert Y_i - \hat{Y}_i \rvert
				\end{displaymath}
				čím sa ale zmení odvodenie normálnych rovníc pre výpočet parametrov. 

				Model lineárnej regresie je pomerne jednoduchý a skutočné dáta častokrát opisujú zložitejšie nelineárne funkcie. Medzi komplexnejšie
				modely pre regresiu, ktoré si dokážu poradiť s nelineárne závislými dátami, patria napríklad neurónové siete, generalizovaná lineárna regresia s
				bázovými funkciami, \emph{Support Vector Machines} s použitím nelineárneho kernelu.

			\subsubsection{Klasifikácia}
				Ako je aj z úvodného príkladu zrejmé, pri klasifikačnej úlohe je cieľom roztriediť vstupné inštancie dát do viacerých tried. Na riešenie
				klasifikácie je tiež možné použiť lineárny model, avšak s niekoľkými úpravami. 

				Pre výstupné kategórie nemôžeme priamo v modely použiť slovné označenie, preto použijeme numerické. Pre zjednodušenie uvažujme 
				dve výstupné triedy (kategórie) dát, ktoré budú reprezentované číslami $0, 1$ (teda napríklad $\text{pošta} = 1, \text{spam} = 0$). 
				Takže $Y_i \in \{0, 1\}$. Vstupné dáta majú rovnakú formu ako pri regresii a ostáva už len natrénovať model na klasifikáciu rovnakým 
				spôsobom, ako to bolo pre regresiu (rozdiel je len vo výstupoch). 
				
				Stále však treba určiť interpretáciu výstupov tak, aby sme dostali pre každú dátovú inštanciu (dátový bod, príklad, riadok) jednoznačné 
				priradenie do jednej triedy. Na to môžeme použiť pravidlo 
				\begin{gather*}
					(X_i, \hat{Y_i}) \in Trieda 1 \quad ak\quad \hat{Y} > 0.5 \\
					(X_i, \hat{Y_i}) \in Trieda 2 \quad ak\quad \hat{Y} \le 0.5
				\end{gather*}
				
				Pri použití lineárneho modelu pre klasifikáciu sme natrénovali lineárny diskriminant $X^T\Theta = 0.5$ ktorý predstavuje deliacu
				nadrovinu v danom $(n+1)$-rozmernom priestore dát a oddeľuje tak dáta na dve triedy \cite{stat-learn}. Všetky dátové body, ktoré sa nachádzajú
				na jednej strane nadroviny, sú klasifikované do jednej triedy, a dátové body z druhej strany nadroviny padnú do druhej triedy.
				Pri zložitejších dátach, ktoré nie je možné lineárne separovať, budú ale niektoré dátové body nesprávne klasifikované, preto sa
				používajú zložitejšie nelineárne modely podobne ako pre regresiu.

		\subsection{Učenie bez učiteľa (unsupervised learning)}

			Učenie bez učiteľa sa používa na riešenie problémov, pri ktorých nemáme pre vstupné dáta výstupné hodnoty. Chceme sa dozvedieť niečo
			o štruktúre a skrytých vzoroch v dátach (distribúcia, topológia, podobnosť alebo odlišnosť skupín dát medzi sebou apod.). Opäť máme sadu
			vstupných dát vo forme $n$-rozmerných vektorov $X_i = (x_1, x_2, \ldots, x_n)$, $X_i \in \mathbb{R}^n$. Nemáme však výstupnú hodnotu
			$Y_i$, a teda ani spôsob, ako určiť kvalitu modelu pomocou chybovej funkcie. 

			Medzi aplikácie učenia bez učiteľa patrí napríklad kompresia dát, hľadanie odlišností od normálu (hľadanie \emph{outliers}, napríklad pri procese 
			výroby a testovania produktov), \emph{data mining} (analýza dát) a iné. Dáta sú často reprezentované ako body v $n$-rozmernom priestore.

			Pri učení bez učiteľa sa model netrénuje v takom zmysle, ako sa trénoval model učenia s učiteľom. Algoritmus učenia bez učiteľa dostane na vstupe
			priamo dáta, z ktorých chceme, aby spočítal nami požadovaný výsledok a učí sa teda priamo na skutočných dátach. Nemáme trénovaciu a testovaciu
			množinu, rovnako ako nemáme priamy spôsob, ktorým ohodnotiť kvalitu modelu (chybovú funkciu) pretože nemáme učiteľský signál s ktorým by 
			sme model porovnávali \cite{stat-learn}.

			\subsubsection{Klastrovanie (zhlukovanie) a algoritmus K-means}
				\emph{K-means} algoritmus sa používa na riešenie následujúcej modelovej situácie: na vstupe máme $t$ dátových bodov, ktorých atribúty sú kvantitatívneho 
				charakteru, a na výstupe chceme mať $k$ disjunktných oblastí, do ktorých sú dátové body rozdelené na základe väčšej miery podobnosti medzi sebou 
				v rámci jednej skupiny, ako medzi bodmi rôznych skupín. Dátové body jednej skupiny sa teda na seba podobajú viac, ako sa podobajú na body iných skupín 
				\cite{stat-learn}. 
				
				Formálnejšie, požadujeme $k$ \emph{centroidov}, $\Delta_1, \Delta_2, \ldots, \Delta_k$, teda bodov, z ktorých každý reprezentuje jednu 
				oblasť, skupinu (je to centrálny bod oblasti, preto \emph{centroid}), a vektor priradení $C = (c_1, c_2, \ldots, c_i, \ldots, c_t), c_i \in {1, \ldots, k}$ 
				každého z $t$ dátových bodov $X_i$ ku $c_i$-tému centroidu.

				Metrika, ktorou meriame podobnosť dvoch bodov môže byť rôzna, v ďalšom však bude použitá \emph{euklidovská vzdialenosť}.

				Cieľom teda je minimalizovať funkciu:
				\begin{displaymath}
					F(\Gamma, C) = \sum_{i=1}^{k}\sum_{j:c_j = i} \lVert{X_j - \Delta_i}\rVert^2
				\end{displaymath}
				kde $\Gamma$ je vektor centroidov, $C$ je vektor priradení dátových bodov ku centroidom, $X_j$ je dátový bod a $\Delta_i$ je centroid,
				ku ktorému je priradený. Výraz $j:c_j = i$ znamená ``všetky $j$ pre ktoré $c_j = i$'', teda vyberáme postupne pre každý centroid jemu priradené
				dátové body.

				Samotný algoritmus K-means má tieto časti:
				\begin{enumerate}
					\item{Inicializácia}
					
						Je potrebné nájsť počiatočné centroidy. Tieto sú buď vygenerované náhodne, alebo sa použije nejaká heuristika pre ich
						počiatočnú hodnotu.
					\item{Iterácia}

						Pojmom \emph{iterácia} sa označuje krok algoritmu, ktorý je opakovaný niekoľkokrát vždy s novými vstupnými parametrami. 
						Algoritmus K-means má tento krok výpočtu následovný:
						\begin{enumerate}
							\renewcommand{\labelenumii}{\theenumii}
							\renewcommand{\theenumii}{\theenumi.\arabic{enumii}.}
							\item{Každý bod $X_i$ priradíme k najbližšiemu centroidu}

								Vykonáme teda priradenie 
								\begin{displaymath}
									c_i = \argmin_j \lVert X_i - \Delta_j \rVert^2
								\end{displaymath}
								kde $\argmin$ znamená výber argumentu (v našom prípade $j$), ktorý minimalizuje funkciu za ním. Inými slovami,
								do $c_i$ je priradená taká hodnota argumentu $j$, pre ktorú je funkcia $\lVert X_i - \Delta_j \rVert^2$ minimálna.
							\item{Vypočítajú sa nové centroidy}
							
								Teraz je treba vypočítať nové centroidy, ako priemer všetkých bodov priradených do jednej množiny, pre každý centroid
								a jeho množinu bodov:
								\begin{displaymath}
									\Delta_j = avg_{i:c_i = j}(X_i)
								\end{displaymath}								
						\end{enumerate}
				\end{enumerate}

				Iterácia sa opakuje kým dochádza ku nejakým zmenám priradení bodov ku centroidom. Otázkou ostáva, ako tento algoritmus minimalizuje funkciu
				$F(\Gamma, C)$? S vykonaním dostatočného množstva iterácií, aj pre rôzne počiatočné centroidy je zrejme možné nájsť aj optimálne riešenie. Avšak každá
				iterácia zlepšuje výsledok, čo sa dá matematicky popísať. Na to, aby sme našli lokálny extrém funkcie, potrebujeme nájsť body v ktorých je jej prvá derivácia 
				rovná nule. Uvažujme v ďalšom len jeden centroid $\Delta$:
				\begin{displaymath}
					\frac{d \sum_{i = 1}^{t} \lVert{X_i - \Delta}\rVert^2}{d\Delta} = \sum_{i=1}^{t}(2(X_i - \Delta)1) = 2\sum_{i=1}^{t}X_i - 2\sum_{i=1}^{t}\Delta = 
					2\sum_{i=1}^{t}X_i - 2t\Delta
				\end{displaymath}								
				
				Derivovanú funkciu položíme rovnú nule a riešime rovnicu:
				\begin{gather*}
					2\sum_{i=1}^{t}X_i - 2t\Delta = 0 \\
					\sum_{i=1}^{t}X_i - t\Delta = 0 \qquad / * \frac{1}{2} \\
					- t\Delta = -\sum_{i=1}^{t}X_i \qquad / - \sum_{i=1}^{t}X_i \\
					\Delta = \frac{\sum_{i=1}^{t}X_i}{t} \qquad / * (-\frac{1}{t})
				\end{gather*}

				Posledný riadok úpravy nám hovorí, že keď vyberieme nový centroid $\Delta = \frac{\sum_{i=1}^{t}X_i}{t}$, zároveň minimalizujeme
				vzdialenosť všetkých dátových bodov (priradených ku starému centroidu) od nového centroidu. $\Delta = \frac{\sum_{i=1}^{t}X_i}{t}$
				však nie je nič iné, ako priemer cez všetky body priradené ku centroidu, čo je presne to, čo robíme v algoritme v časti 2.2.

				Ukázali sme, že každým krokom minimalizujeme odlišnosti bodov priradených ku jednému centroidu a teda sa približujeme ku riešeniu. 
				Pre matematickú korektnosť je potrebné dodať, že položením derivácie rovnej nule nájdeme len lokálne extrémy funkcie. Či sa jedná o 
				minimum (ktoré sme v predošlom predpokladali) sa dá overiť položením druhej derivácie v danom bode rovnej nule. 
				Pri dôkaze pre viac centroidov by bolo nutné použiť parciálnu deriváciu, výsledok by však bol rovnaký.

				Algoritmus konverguje a teda vždy nájde riešenie. Nemusí ísť ale o optimálne riešenie, mohlo sa stať že ide o lokálne minimum.
				Preto sa v praxi niekoľkokrát opakuje vždy s iným počiatočným rozmiestnením centroidov a vyberie sa rozloženie s najmenším 
				výsledkom funkcie $F(\Gamma, C)$ \cite{stat-learn}.

				Zaujímavou otázkou je aj to, ako vhodne vybrať počet segmentov $k$. Existujú heuristiky, ktoré sa pokúšajú nájsť optimálne $k$
				pre dané dáta, zdá sa však, že univerzálne pravidlo neexistuje. 

			%\subsubsection{Redukcia dimenzionality a analýza hlavných komponentov (Principal component analysis)}
				%\todo[inline]{Daniel: zatiaľ preskakujem, nemám dobré podklady (alebo im nerozumiem)}

			%\subsubsection{Samo-organizujúce sa mapy (Self-organizing maps)}
				%\todo[inline]{Daniel: zatiaľ preskakujem, možno to bude súčasť sekcie Neurónové siete}

    		%\subsection{Reinforcement learning (len stručne zatiaľ)}
    
  	%\section{Learning theory - vlastnosti algoritmov strojového učenia, teória o dátach, o funkciách ktoré sa dajú učiť, atď}

	\section{Neurónové siete}

		Moderná história teórie neurónových sietí sa začala písať v 40-tych rokoch minulého storočia. Na rozvoji tejto oblasti sa tiež podieľalo veľa
		významných teoretikov a vedeckých osobností, ako napríklad W. McCulloch, W. Pitts, F. Rosenblatt, N. Wiener, M. Minski, J. von Neumann, D. Hebb, 
		D. Gabor, W. R. Ashby a mnoho ďalších \cite{neur-nets} .

		\subsection{Biologická podstata modelu}
			Model umelých neurónových sietí vychádza z biologickej podstaty nervovej sústavy, mozgu, neurónov a nervových prepojení. Ľudský mozog
			pozostáva z približne $10^{11}$ neurónov, ktoré sú prepojené rádovo $10^{14}$  spojeniami. Pochody na nervovej úrovni sú typicky
			o 5-6 rádov pomalšie (milisekundy) ako pochody na kremíkovom čipe (nanosekundy). Mozog má ale stále pred kremíkovím čipom obrovský 
			náskok, najmä vďaka ohromnému počtu neurónov a ešte väčšiemu počtu prepojení, ktorých výsledkom je masívny paralelizmus. Za zmienku
			stojí aj rádovo väčšia energetická efektívnosť biologického mozgu oproti kremíkovým čipom. \cite{neur-nets}

			Interakcie medzi biologickými neurónmi sa odohrávajú pomocou prepojení, \emph{synapsí}. Tieto fungujú na princípe elektro-chemického
			prenosu - elektrický potenciál na jednej strane synapse spôsobí uvoľnenie \emph{neurotransmitteru}, ktorý sa rozptýli do medzi-synaptického priestoru
			a na druhej strane synapse, po naviazaní na receptory, odštartuje postsynaptický proces a šírenie signálu pokračuje cez ďalší neurón.
			%\todo[inline]{Daniel: možno obrázok}

			Elektrický potenciál, ktorý sa šíri po membráne axónu neurónu (najdlhší výbežok neurónu), %\todo[inline]{Daniel: Obrázok} 
			sa nazýva \emph{akčný potenciál}. 
			Aby došlo ku vzniku tohoto potenciálu (neurón je v excitovanom stave, šíri signál, \emph{páli} z angl. \emph{to fire}) musí dôjsť ku jeho stimulácií zo 
			vstupných synapsí (v špeciálnom prípade sa môže neurón aktivovať aj spontánne). Táto stimulácia môže byť dvojaká - buď cez jednu synapsu príde 
			niekoľko signálov za sebou (temporálna stimulácia) alebo z viacerých synapsí dorazia signály v dostatočnom množstve naraz (priestorová stimulácia). 
			Ak potenciál membrány prekročí excitačný prah, v neuróne vznikne nový signál (akčný potenciál) ktorý sa šíri ďalej cez axón do ďalších neurónov.	
			
		\subsection{Model umelého neurónu}

			Tak ako biologický neurón je základnou stavebnou jednotkou biologického nervového systému, umelý neurón je základnou stavebnou jednotkou umelej 
			neurónovej siete. Umelý neurón má tieto základné časti \cite{neur-nets}:

			\begin{itemize}
				\item{Vstupné synaptické spojenia}

					Do umelého neurónu vstupuje $n$ vstupných signálov (vektor vstupných dát $X \in \mathbb{R}^n$, $X = (x_1, x_2, \ldots, x_n)$). Tieto môžu 
					pochádzať priamo z prostredia, čo sa dá chápať ako analógia s lineárnym modelom učenia s učiteľom - vstupy neurónu sú sémanticky totožné so 
					vstupmi lineárneho modelu pre regresiu alebo klasifikáciu, ktorý už bol popísaný. Rovnako ide o zjednodušenú analógiu s biologickým 
					modelom - vstupné spojenia predstavujú príchodzie synapse na biologickom neuróne. Vstupné dáta ale môžu pochádzať aj od predošlej vrstvy 
					neurónov, vo viacvrstvovom modely, ktorý bude popísaný neskôr.
				\item{Vektor váh na vstupné synapse}

					Pre každú vstupnú synapsu má umelý neurón tzv. \emph{váhu}, teda volne povedané faktor, ktorý reprezentuje prínos daného vstupu pre výstup
					neurónu ako celku. Pre umelý neurón teda máme vektor váh $W \in \mathbb{R}^n$, $W = (w_1, w_2, \ldots, w_n)$.
				\item{Sumačná jednotka}

					Všetky vstupy sa po aplikovaní váh (prenásobení príslušnými vstupnými váhami) sumujú v sumačnej jednotke, čo reprezentuje lineárnu
					kombináciu všetkých vstupov, zjednodušenú analógiu ku biologickému princípu membránového potenciálu neurónu. Výstup sumačnej jednotky umelého
					neurónu teda je 
					\begin{displaymath}
						sum = \sum_{i = 1}^{n}w_ix_i
					\end{displaymath}
					čo sa dá vyjadriť v maticovom zápise ako
					\begin{displaymath}
						sum = W^TX
					\end{displaymath}
				\item{Aktivačná funkcia $\varphi$}

					Nakoniec, výsledok zo sumačnej jednotky prejde cez aktivačnú funkciu, ktorej úlohou je limitovať výstup neurónu do uzatvoreného intervalu
					(napríklad $(-1\ldots1)$, alebo $(0\ldots1)$). Následujúce funkcie sú príkladmi aktivačných funkcií:
					\begin{itemize}
						\item{Prahová (threshold) funkcia}

							\begin{displaymath}
								\varphi(sum) = 
								\begin{cases}
									1 &\mbox{if} \quad sum \geq 0 \\
									0 &\mbox{if} \quad sum < 0
								\end{cases}
							\end{displaymath}
							%\todo[inline]{Daniel: Obrázok}
						\item{Po častiach lineárna funkcia (piecewise-linear function)}

							\begin{displaymath}
								\varphi(sum) = 
								\begin{cases}
									1 &\mbox{if} \quad sum \geq \frac{1}{2} \\
									sum &\mbox{if} -\frac{1}{2} < sum < \frac{1}{2}\\	
									0 &\mbox{if} \quad sum < -\frac{1}{2}
								\end{cases}
							\end{displaymath}
							%\todo[inline]{Daniel: Obrázok}
						\item{Sigmoidálna funkcia}

							Táto trieda funkcií patrí medzi najpoužívanejšie v kontexte neurónových sietí. Vo všeobecnosti má sigmoida graf tvaru ležatého S, 
							pričom je striktne rastúca. Príkladom je \emph{logistická funkcia}
							\begin{displaymath}
								\varphi(sum) = \frac{1}{1 + e^{-sum}}
							\end{displaymath}
							Na sigmoidách je navyše podstatné aj to, že sú nelineárne a derivovateľné vo všetkých bodoch (čo je podstatné pri učení viacvrstvových 
							modelov neurónových sietí, ktoré budú spomenuté neskôr). Iným príkladom takejto funkcie je $f(sum) = \tanh(sum)$, ktorej hodnoty sú 
							z intervalu $(-1\ldots 1)$, čo má v istých oblastiach výhody nad rozsahom hodnôt logisitckej funkcie, ktorý je $(0\ldots 1)$.
							%\todo[inline]{Daniel: Obrázok}
					\end{itemize}

				Výstup neurónu po aplikovaní aktivačnej funkcie má teda tvar
				\begin{displaymath}
					\hat{Y} = \varphi(sum) = \varphi(W^TX)
				\end{displaymath}
			\end{itemize}

			V prípade, že je neurón používaný na klasifikačnú úlohu, je možné použiť \emph{softmax} aktivačnú funkciu na výstupe, alebo interpretovať výstup spojitej
			sigmoidy do dvoch tried (napríklad prahovaním: $x = y > 0.5$, pričom $x$ nadobúda hodnoty \emph{true}, \emph{false}, ktoré je možné ďalej interpretovať
			ako trieda 1 a trieda 2). 

			Pre sieť neurónov je možné použiť tzv. \emph{one-hot} kódovanie, ktorého princípom je mať viac výstupných neurónov (toľko, koľko tried dát je na vstupe) 
			a pre každú triedu sa po natrénovaní aktivuje práve jeden a vždy ten istý neurón (napríklad výstup aktivačnej funkcie tohoto neurónu je blízky $1$).
			
			Dôležitou súčasťou umelého neurónu je, podobne ako pri lineárnom regresnom modely, pridanie výchylky (\emph{bias}) do vektoru vstupov a jeho váhy do 
			vektoru váh. Umelo sme teda pridali jednu synapsu aj s váhou, pričom vstupná hodnota synapse bude $x_0 = 1$ (alternatívne $x_0 = -1$) a jej váha 
			$w_0 = bias$ (skutočná hodnota výchylky) sa natrénuje spolu s ostatnými váhami počas trénovania neurónu. 
			
			Význam biasu, podobne ako pri lineárnom regresnom modely, je aplikovať afinnú transformáciu na výstup sumačnej funkcie, čo spôsobí, že graf výsledku 
			sumačnej funkcie proti výsledku sumačnej funkcie s pridaným biasom už neprechádza nulou \cite{neur-nets}. 
			%\todo[inline]{Daniel: Hodil by sa obrázok}

			Pridanie vstupu $x_0$ a váhy $w_0$ ku vektoru vstupov $X$ a vektoru váh $W$ zmení vzťah pre výpočet výstupu sumačnej jednotky následovne
			\begin{displaymath}
				sum = \sum_{i = 0}^{n}w_ix_i
			\end{displaymath}
			Na tento vzťah sa však už bude dať pozerať aj takto
			\begin{displaymath}
				sum = \sum_{i = 1}^{n}w_ix_i + bias
			\end{displaymath}
			Nepatrnou zmenou tiež prejdú aj definície oboch vektorov, pričom konštrukcia ich nového znenia je ponechaná na čitateľovi.

			Schematická ilustrácia modelu umelého neurónu je na \hyperlink{perceptron}{Obr. \ref{fig:stroj_uc_1}}		
			\begin{figure}[htp]
				\centering
				\includegraphics[scale=0.5]{images/Perceptron}		
				\caption{Ilustrácia modelu umelého neurónu}
				\hypertarget{perceptron}{}
				\label{fig:stroj_uc_1}
			\end{figure}

		\subsection{Architektúry neurónových sietí}
			
			V oblasti umelých neurónových sietí sa používa viacero architektúr. Základná idea je ale podobná pre všetky - siete sú štruktúrované do vrstiev neurónov,
			pričom prepojenie jednotlivých vrstiev v rámci architektúry sa odráža aj na algoritme, ktorým je daná sieť danej architektúry trénovaná. 

			Vo všeobecnosti existujú tri základné architektúry neurónových sietí \cite{neur-nets}
			\begin{itemize}
				\item{Jednovrstvová dopredná architektúra}
				\item{Viacvrstvová dopredná architektúra}
				\item{Rekurentná architektúra}
			\end{itemize}

			Každá má odlišné vlastnosti, iný algoritmus trénovania a dá sa ňou riešiť iná skupina problémov. Neurónové siete vystupujú v kontexte učenia s učiteľom, 
			rovnako ako aj v kontexte učenia bez učiteľa. Používajú sa ako na regresné, tak aj na klasifikačné úlohy. Jedno z dôležitých tvrdení o neurónových 
			sieťach (priamo aplikovateľné na viacvrstvový model používajúci nelineárnu, ohraničenú a rastúcu aktivačnú funkciu natrénovaný algoritmom spätného 
			šírenia chyby) je teoréma o univerzálnej aproximácií - neurónová sieť dokáže aproximovať ľubovolnú spojitú funkciu \cite{neur-nets}.

			Existuje aj viac prístupov ku trénovaniu neurónových sietí - napríklad \emph{Error-correction learning}, teda učenie iteratívnym opravovaním chyby
			siete, \emph{Hebbovské učenie}, založené na pozorovaní selektívnej úpravy synaptických váh medzi biologickými neurónmi, \emph{kompetitívne učenie}
			a ďalšie. 

		\subsection{Jednovrstvová dopredná sieť}

			Jednovrstvová dopredná sieť sa skladá zo vstupnej vrstvy a za ňou následujúcej výstupnej vrstvy neurónov. Vstupná vrstva plní len funkciu reprezentácie 
			dátového bodu, formálne sa teda dá popísať opäť ako vektor $n$ vstupov $X\in\mathbb{R}^{n+1}$, $X = (x_0, x_1, \ldots, x_n)$ s už pridanou výchylkou 
			$x_0 = 1$ (alternatívne $x_0 = -1$). 

			Vrstva výstupných neurónov obsahuje konečný počet neurónov $k$, pričom štruktúra jednotlivých neurónov odpovedá popísanému modelu umelého neurónu. 
			V ďalšom budeme uvažovať, že každý neurón má v rámci siete spojenie na všetky vstupy. $i$-ty neurón má teda svoj vektor váh 
			$W_i \in \mathbb{R}^{n+1}$, $W_i = (w_{i0}, w_{i1}. \ldots, w_{in})$.	Ďalej má sumačnú jednotku, ktorá počíta hodnotu $sum = X^TW_i$ a aktivačnú 
			funkciu $\varphi$. Aktivácia, resp. výstup $i$-teho neurónu má teda tvar $\hat{Y}_i = \varphi(sum)$.

			Označme maticu $W$ ako maticu váh \emph{všetkých} neurónov siete. $W$ teda obsahuje $k$ riadkov a $(n+1)$ stĺpcov. Ďalej označme vektor $\hat{O}$ ako vektor 
			výstupov všetkých neurónov, $\hat{O} = (\hat{Y}_1, \ldots, \hat{Y}_k)$.

			Ilustračná schéma jednovrstvovej architektúry je zobrazená na \hyperlink{jednovrst}{Obr. \ref{fig:stroj_uc_3}}
			\begin{figure}[htp]
				\centering
				\includegraphics[scale=0.55]{images/Jednovrst_siet}		
				\caption{Ilustrácia jednovrstvovej architektúry neurónovej siete}
				\hypertarget{jednovrst}{}
				\label{fig:stroj_uc_3}
			\end{figure}

			Rovnica pre výpočet výstupu siete ako celku má teda tvar
			\begin{displaymath}
				\hat{O} = \varphi(X^TW^T)
			\end{displaymath}
			pričom aktivačná funkcia sa aplikuje zvlášť na každú zložku výsledného vektora maticového súčinu.

			\subsubsection{Trénovanie siete}
				Error-correction algoritmus pre trénovanie jednovrstvovej siete má následovnú štruktúru
				\begin{enumerate}
					\item{Inicializácia}

						Nastavenie matice váh na počiatočné hodnoty - napríklad náhodné hodnoty z intervalu $0 \ldots 1$, alebo nulový vektor \cite{neur-nets}. 
						Použitie príliš veľkých hodnôt môže spomaliť učenie, napríklad pri použití logistickej aktivačnej funkcie, ktorá je pre veľké vstupné hodnoty 
						blízka konštante. Je tiež dobré normalizovať dáta, ako už bolo spomenuté.
					\item{Iterácia}

						Tiež nazývaná ako \emph{epocha} algoritmu. Na začiatku každej epochy je potrebné zabezpečiť náhodné poradie trénovacích príkladov. 
						Použitie vždy toho istého poradia môže ovplyvniť trénovanie, obzvlášť ak sú dáta napríklad zoradené. Nasleduje cyklus cez všetky dátové body
						trénovacej množiny (každý je teda použitý práve raz), počas ktorého sa vykoná následovné
					\begin{enumerate}
						\renewcommand{\labelenumii}{\theenumii}
						\renewcommand{\theenumii}{\theenumi.\arabic{enumii}.}
						\item{Výber dátového bodu z trénovacej množiny}
						\item{Výpočet aktivácie siete}
						\item{Výpočet chyby od cieľovej hodnoty pre daný dátový bod}
						\item{Úprava váh neurónov na základe chyby na momentálnom dátovom bode a \emph{učiaceho pravidla}}
					\end{enumerate}
				\end{enumerate}

				Algoritmus môže mať rôzne podmienky pre ukončenie - napríklad pevný počet epoch, dosiahnutie určitej hodnoty chyby epochy (chyba epochy je suma
				chýb siete (kvadratických) na jednotlivých dátových príkladoch, pre všetky dátové príklady v rámci danej epochy) alebo iné kritérium.

				Chyba siete na konkrétnom dátovom príklade má tvar $(Y - \hat{O})$, kde $Y$ je cieľová hodnota pre daný dátový bod. Minimalizáciou funkcie
				\begin{displaymath}
					Err = \frac{1}{2}(\hat{O} - Y)^2
				\end{displaymath}
				sa dostaneme ku učiacemu pravidlu a ku algoritmu \emph{least-mean-square} pre trénovanie jednovrstvovej siete \cite{neur-nets}. Algoritmus vychádza z metódy
				\emph{najstrmšieho zostupu}, kedy sa vo váhovom priestore každou iteráciou pomocou učiaceho pravidla pohybujeme ku (potenciálne lokálnemu)
				minimu v smere, ktorý je opačný gradientu funkcie $Err$ podľa vektora váh (pri výpočte pre jeden neurón). Iný príklad chybovej funkcie je 
				napríklad \emph{cross-entropy} chyba. Použitie inej chybovej funkcie má za následok zmenu učiaceho pravidla.

				Pre doplnenie, iné metódy ktorými je možné odvodiť učiace pravidlá sú napríklad \emph{Newtonova metóda} alebo \emph{Gauss-Newtonova metóda} 
				\cite{neur-nets}.

				Po výpočte chyby v danom dátovom bode upravíme váhovú maticu siete, avšak len v prípade nenulovej chyby od cieľovej hodnoty. Učiace
				pravidlo býva označované aj ako \emph{delta pravidlo}, a v prípade nami použitej chybovej funkcie $Err$ a metódy \emph{najstrmšieho zostupu} má tvar
				\begin{displaymath}
					W_{n+1} = W_{n} + \alpha(Y - \hat{O})\varphi'(sum)X^T
				\end{displaymath}
				kde $W_{n+1}$ označuje novú hodnotu váh, $W_{n}$ súčasnú hodnotu, $\alpha$ označuje \emph{rýchlosť učenia}. $sum$ je výsledok sumačnej 
				jednotky, ktorý vznikol pri výpočte aktivácie siete. Premenné $\hat{O}, Y, sum$ môžu byť skalárne (v prípade siete, ktorá obsahuje len jeden neurón) 
				alebo vektory (ak sieť obsahuje viac neurónov). Treba upozorniť, že v prípade siete obsahujúcej viac neurónov je rovnica len schematická - operácia
				$(Y - \hat{O})\varphi'(sum)$ by bola medzi dvoma vektormi s rovnakým počtom komponentov a vyjadrovala by násobenie vektorov po zložkách.

				Pre názornosť, derivácia logistickej funkcie má tvar
				\begin{displaymath}
					logsig(x)' = logsig(x)(1-logsig(x))
				\end{displaymath}

				Rýchlosť učenia $\alpha$ je kladné číslo, $0 < \alpha$, typicky okolo $0.3$. Ovplyvňuje rýchlosť konvergencie algoritmu do (potenciálne lokálneho)
				minima v priestore váh. Upravuje veľkosť jedného kroku v smere najstrmšieho zostupu. Príliš veľké $\alpha$ môže spôsobiť divergenciu algoritmu, zatiaľ
				čo príliš malá hodnota môže spomaliť trénovanie.
				
				Najjednoduchšia jednovrstvová sieť, ktorá obsahuje len jeden neurón s prahovaciou aktivačnou funkciou na účel binárnej klasifikácie lineárne separovateľných
				tried sa nazýva \emph{perceptrón}. Označenie perceptrón pre umelý neurón je výstižnejšie a uprednostňované, pretože model umelého neurónu pochádza 
				z práce F. Rosenblatta, ktorý pomenovanie použil. Učiace pravidlo má v tomto prípade tvar %nedostal som sa ku fulltext článku, takže neviem čo presne citovať
				\begin{displaymath}
					W_{n+1} = W_{n} + \alpha(Y - \hat{O})X^T
				\end{displaymath}
				Jednovrstvová sieť $k$ perceptrónov nám umožňuje klasifikovať $2^k$ dátových tried, ktoré však musia byť lineárne separovateľné (dátové body 
				jednotlivých tried  sú oddeliteľné nadrovinou v dátovom priestore \cite{neur-nets}).  To je ale málokedy postačujúce pre dáta z praxe. Táto 
				vlastnosť jednovrstvovej architektúry stála za odvrátením pozornosti od	neurónových sietí v období 70-tych rokov minulého storočia. Záujem o 
				neurónové siete opäť ožil až s prekonaním tohoto nedostatku viacvrstvovou architektúrou a algoritmom \emph{spätného šírenia chyby}.

			\subsubsection{Viacvrstvová dopredná sieť}

				Viacvrstvová architektúra obsahuje okrem vstupnej a výstupnej vrstvy ešte aspoň jednu \emph{skrytú vrstvu} neurónov \cite{neur-nets}. Skryté vrstvy 
				sa nachádzajú medzi vstupnou a výstupnou vrstvou. Vrstvy siete sú usporiadané, takže pri výpočte výstupu siete ako aj pri úprave váh počas 
				trénovania algoritmus postupuje od jednej vrstvy ku druhej, pričom výstup predošlej vrstvy je vstupom následujúcej. 

				Výpočet výstupu viacvrstvovej siete začína od prvej skrytej vrstvy (keďže \emph{vstupná vrstva} je len označenie pre dátový bod a de facto 
				nevykonáva žiadny výpočet), pokračuje následujúcou vrstvou a tak ďalej, až ku poslednej, výstupnej vrstve. Preto je táto architektúra označovaná 
				ako \emph{dopredná}.

				Ďalšou hlavnou súčasťou siete je nelineárna aktivačná funkcia, ktorá je derivovateľná vo všetkých bodoch \cite{neur-nets}. Viacvrstvová architektúra 
				býva označená aj ako \emph{MLP}, teda \emph{Multi-layer perceptrons} \cite{neur-nets}.

				Základný a často používaný \emph{error-correction} algoritmus pre trénovanie viacvrstvovej siete sa volá \emph{error back-propagation}, teda algoritmus
				\emph{spätného šírenia chyby} \cite{neur-nets}. Chybu siete pri trénovaní na výstupnej vrstve vieme vypočítať rovnako ako v jednovrstvovom modely, 
				avšak chyba výstupu skrytej vrstvy nie je taká jasná - pre skrytú vrstvu totiž nemáme žiadny učiteľský signál. Chyba siete od požadovaného výstupu sa ale dá
				spätne propagovať od výstupnej vrstvy cez všetky skryté vrstvy. 
				
				Označenie \emph{spätného šírenia} vyplýva z opačného smeru prechodu sieťou pri výpočte a aplikácií chyby ako pri výpočte výstupu siete, teda od výstupnej 
				vrstvy po prvú skrytú vrstvu.

				Označme $n$-rozmerný vstup siete vektorom $X$, $X\in\mathbb{R}^{(n + 1)}$, čiže $X = (x_0, \ldots, x_n)$ s už pridanou výchylkou (bias) $x_0 = 1$. Ďalej
				predpokladajme, že naša sieť má $h$ skrytých vrstiev neurónov, pričom každá má $k_i$ neurónov, $i\in 1, \ldots, h$. Označme maticu $W_i$ maticou 
				váh $i$-tej skrytej vrstvy, $sum_i$ nech je $k_i$-prvkovým vektorom výstupov sumačných jednotiek $i$-tej skrytej vrstvy. $W_i$ má $k_i$ riadkov a 
				$k_{i-1} + 1$ stĺpcov pre $i\in 2, \ldots, h$. Matica $W_1$ má $(n + 1)$ stĺpcov a $k_1$ riadkov. Ďalej označme $(k_i + 1)$-prvkový vektor $\hat{Y}_i$ 
				vektorom výstupov $k_i$-tej skrytej vrstvy, s už pridanou výchylkou pre vstup do ďalšej vrstvy. 

				Nech výstupná vrstva má $v$ neurónov. Označme $W_o$ maticou váh výstupnej vrstvy, ktorá má $v$ riadkov a $k_h + 1$ stĺpcov. Vstupy poslednej
				vrstvy sú uložené vo vektore $\hat{Y}_h$, $sum_o$ označuje vektor obsahujúci výsledky sumačných jednotiek výstupných neurónov. Ako posledné označme 
				výstup výstupnej vrstvy (a teda siete ako celku) $v$-prvkovým vektorom $\hat{O}$, učiteľský signál ako $Y$ a aktivačné funkcie jednotlivých skrytých 
				vrstiev ako $\varphi_i, i \in 1,\ldots,h$ a aktivačnú funkciu výstupnej vrstvy $\varphi_o$.

				Je potrebné zdôrazniť, že matica váh vrstvy je vektorom ak má vrstva len jeden neurón, pričom v tomto prípade je výstup tejto vrstvy skalárna hodnota. 
				Tieto skutočnosti treba brať do úvahy pri konkrétnych sieťach.

				Ilustračná schéma viacvrstvovej architektúry je zobrazená na \hyperlink{viacvrst}{Obr. \ref{fig:stroj_uc_4}}
				\begin{figure}[htp]
					\centering
					\includegraphics[scale=0.55]{images/Viacvrst_siet}		
					\caption{Ilustrácia viacvrstvovej architektúry neurónovej siete}
					\hypertarget{viacvrst}{}
					\label{fig:stroj_uc_4}
				\end{figure}

				Výstup siete ako celku sa vypočíta rovnakou schematickou rovnicou ako pri jednovrstvovej sieti, teraz je však potrebné postupne prejsť cez všetky 
				vrstvy, pričom vstup vrstvy je výstup predošlej vrstvy (v prípade prvej skrytej vrstvy je vstupom dátový bod). 
				\begin{gather*}
					\hat{O} = \varphi_o(\hat{Y_h}^TW_o^T) \\
					\hat{Y_i} = \varphi_i(\hat{Y_{i - 1}}^TW_i^T)\quad\text{pre}\quad i \in 2,\ldots,h \\
					\hat{Y_1} = \varphi_1(X^TW_1^T) \\
				\end{gather*}

				Schéma trénovacieho algoritmu spätného šírenia chyby je podobná algoritmu trénovania jednovrstvovej siete, má však niekoľko kľúčových rozšírení
				\begin{enumerate}
					\item{Inicializácia}

						Nastavenie váh \emph{všetkých} vrstiev na náhodné hodnoty, normalizácia trénovacích dát.
					\item{Iterácia (epocha)}

						Zabezpečenie náhodného poradia trénovacích príkladov, ďalej nasleduje cyklus cez všetky trénovacie príklady, každý sa použije práve raz:
						\begin{enumerate}
							\renewcommand{\labelenumii}{\theenumii}
							\renewcommand{\theenumii}{\theenumi.\arabic{enumii}.}
							\item{Výber ďalšieho dátového bodu z trénovacej množiny}
							\item{Výpočet výstupu siete, čo sa označuje ako \emph{forward pass} \cite{neur-nets}, teda dopredný prechod sieťou v smere od 
								vstupnej po výstupnú vrstvu}
							\item{Výpočet chyby siete od požadovaného cieľového výstupu pre daný dátový príklad}
							\item{Spätné šírenie chyby a úprava váh jednotlivých vrstiev siete, na základe \emph{učiaceho pravidla}. Táto časť sa označuje ako
								\emph{backward pass} \cite{neur-nets}, teda spätný prechod sieťou od výstupnej vrstvy po prvú skrytú vrstvu}
						\end{enumerate}
				\end{enumerate}
				
				Opäť môžu byť použité rôzne kritéria pre ukončenie algoritmu, podobne ako pri jednovrstvovej architektúre, napr. pevný počet trénovacích epoch alebo
				dosiahnutie pevne danej chyby siete.

				Pre výstupnú vrstvu vieme chybu vypočítať rovnako ako v jednovrstvovej architektúre, teda $(Y - \hat{O})$. Za predpokladu chybovej funkcie
				\begin{displaymath}
					Err = \frac{1}{2}(\hat{O} - Y)^2
				\end{displaymath}
				a použitia metódy gradientového zostupu na jej iteratívnu minimalizáciu dostávame učiace pravidlo pre výstupnú vrstvu, tentoraz rozdelené na dve časti.

				Označme \emph{delta časť} učiaceho pravidla
				výstupnej vrstvy
				\begin{displaymath}
					\delta_o = (Y - \hat{O})\varphi_o'(sum_o)
				\end{displaymath}
				pričom v prípade viac výstupných neurónov v poslednej vrstve bude medzi operandmi operácia násobenia vektorov po zložkách.

				Učiace pravidlo pre výstupnú vrstvu bude teda rovnaké ako v jednovrstvovej sieti
				\begin{displaymath}
					W^{n+1}_o = W^{n}_o + \alpha\delta_o\hat{Y}_h^T
				\end{displaymath}
				
				Delta časť učiaceho pravidla bude mať v prípade $i$-tej skrytej vrstvy tvar
				\begin{displaymath}
					\delta_i = (W_{i+1}^T\delta_{i+1})\varphi_i'(sum_i)
				\end{displaymath}
				pre $i \in 1,\ldots,h$, pričom index rovný $h + 1$ reprezentuje výstupnú vrstvu.

				Pre $i$-tu skrytú vrstvu vypočítame jej podiel na chybe siete učiacim pravidlom a zmenou váh podla
				\begin{displaymath}
					W^{n+1}_i = W^{n}_i + \alpha\delta_{i}\hat{Y}_{i-1}^T
				\end{displaymath}
				pre $i \in 1,\ldots,h$. Pre $i = 1$ je člen $\hat{Y}_{i-1}^T$ nahradený členom $X^T$. Je potrebné si uvedomiť, že pred samotným prepísaním váh na $i$-tej
				skrytej vrstve alebo na výstupnej vrstve je nutné vypočítať delta časť pravidla vrstvy $i-1$ resp. vrstvy {h}. Alternatívne je možné pri spätnom prechode vypočítať 
				najprv všetky hodnoty $\delta_i, \delta_o$ použitím hodnôt váhových matíc $W_i^{n}, W_o^n$ a až potom naraz vypočítať nové hodnoty matíc 
				$W_i^{n + 1}, W_o^{n + 1}$ podľa učiacich pravidiel. Je potrebné zdôrazniť, že označenie a hodnota váhových matíc $W^{n}, W^{n + 1}$ referuje 
				ku dvom po sebe idúcim krokom cyklu v rámci jednej epochy, teda medzi dvomi po sebe idúcimi trénovacími príkladmi a nemá súvis s počtom prvkov vstupného
				dátového vektora $X$.

				Po výpočte nových váhových matíc všetkých vrstiev siete algoritmus pokračuje ďalším príkladom z trénovacej množiny v rámci danej epochy, resp. novou epochou
				alebo ukončením, ak bol spracovaný posledný trénovací príklad alebo splnená podmienka ukončenia trénovania.

				Na záver je potrebné dodať, že algoritmus spätného šírenia chyby nie je biologicky opodstatnený, na čo existuje niekoľko dôvodov. Učiteľský signál v biologickom
				nervovom systéme neexistuje, takisto spätné šírenie informácie po axóne neurónu sa zdá byť nepravdepodobné. Viacvrstvový perceptrón tiež ignoruje globálnu
				komunikáciu, ktorá sa v biologickom nervovom systéme odohráva napríklad prostredníctvom hormónov, a iné. V žiadnom prípade to však nezmenšuje
				význam tejto architektúry a umelých neurónových sietí v strojovom učení. \cite{neur-nets}

			%\subsubsection{Ďalšie architektúry a použitia neurónových sietí} zrušené pretože architektúry sú už objasnené
			%\subsubsection{Rekurentné neurónové siete} preskakujem kvôli nedostatku času na spracovanie trochu menej jasných podkladov
				%BPTT, RTRL algoritmus	
			%\subsubsection{Neurónové siete pre sekvenčné dáta} zrušené pretože chce ísť o to isté/podmnožinu ako rekurentné siete
				
			
	\section{Rozhodovacie stromy}

		Rozhodovacie stromy predstavujú o niečo odlišnejšiu metódu strojového učenia. Podobne ako predošlé, aj rozhodovacie stromy je možné použiť ako pre
		klasifikačné (teda diskrétne, kvalitatívne) problémy tak pre regresné problémy (spojité, kvantitatívne) \cite{aima:2003}. 

		Rozhodovací strom v princípe predstavuje sériu za sebou idúcich rozhodnutí nad množinou atribútov, ktoré definujú inštanciu pozorovaného javu. 
		Táto séria rozhodnutí vedie ku priradeniu výsledku ku momentálnemu príkladu, v prípade klasifikačnej úlohy zaradenie do niektorej z dátových tried 
		a v prípade regresnej úlohy číselnú hodnotu. Presnejšie povedané, v prípade klasifikácie rozhodovací strom predstavuje funkciu s diskrétnym 
		oborom hodnôt zatiaľ čo v prípade regresnej úlohy rozhodovací strom reprezentuje spojitú funkciou \cite{aima:2003}. Tu je možné si uvedomiť
		analógiu s doterajšími modelmi učenia s učiteľom, kde bolo tiež cieľom natrénovať mapovanie vstupov na výstupy, teda naučenie sa nejakej 
		funkcie. Cieľom rozhodovacích stromov v strojovom učení je predikcia výstupu na základe hodnôt vstupných atribútov.

		Ďalej uvažujme prípad rozhodovacieho stromu pre klasifikačnú úlohu.

		Ilustračným príkladom môže byť rozhodovací strom pre vykonanie prvej pomoci, ktorý by mohol vyzerať napríklad ako\hyperlink{rozhod_strom}{Obr. \ref{fig:stroj_uc_2}}		
		\begin{figure}[htp]
			\centering
			\includegraphics[scale=0.7]{images/Rozhod_strom}		
			\caption{Ilustračný rozhodovací strom pre klasifikáciu účastníkov nehody do priorít ošetrenia}
			\hypertarget{rozhod_strom}{}
			\label{fig:stroj_uc_2}
		\end{figure}
			
		Formálne môže byť rozhodovací strom popísaný ako $n$-árny strom, v ktorom vnútorné vrcholy obsahujú test na vybraný atribút dátového príkladu, hrany
		reprezentujú možné výsledky testu daného atribútu a koncové listy reprezentujú výstupnú hodnotu stromu (v našom prípade dátovú triedu) \cite{aima:2003}.

		Rozhodovacím stromom vieme vyjadriť ľubovolnú \emph{booleovskú} funkciu tak, že každá cesta od koreňa až po list stromu bude reprezentovať jeden riadok
		pravdivostnej tabuľky pre danú funkciu. To ale znamená, že v najhoršom prípade musí strom reprezentovať každý riadok pravdivostnej tabuľky funkcie, aby 
		bolo možné vyjadriť najzložitejšie funkcie. Riadkov v pravdivostnej tabuľke booleovskej funkcie môže byť exponenciálne veľa v závislosti od počtu vstupných atribútov,
		takže je možné ľahko vidieť, že rozhodovacie stromy nie sú dobrou voľbou pre učenie niektorých funkcií. \cite{aima:2003}

		Označme $n$-atribútový vstup rozhodovacieho stromu vektorom $X, X = (x_1, \ldots, x_n)$ a výstupnú hodnotu pre daný strom ako $Y$. Majme $t$-prvkovú 
		trénovaciu množinu dátových príkladov pozostávajúcich zo vstupov $X_i$ a príslušných cieľových hodnôt $Y_i$, $i \in 1, \ldots, t$.

		Jednoduchý rekurzívny algoritmus pre trénovanie rozhodovacieho stromu na základe trénovacej množiny má následovnú štruktúru (vstupom algoritmu je množina 
		dátových príkladov a vrchol stromu, v ktorom sa práve nachádza)
		\begin{enumerate}
			\item{Inicializácia}

				Začni s koreňom stromu a celou trénovacou množinou.
			\item{Telo rekurzie}

				Ak sú v momentálnej množine príklady len jednej triedy, označ vrchol za list s príslušnou triedou a ukonči vetvu rekurzie. 

				Inak vyber \emph{najinformatívnejší} atribút momentálnej množiny príkladov, vlož jeho test do momentálneho (už) vnútorného vrchola, 
				vytvor nové vrcholy spojené s momentálnym hranami reprezentujúcimi možné výsledky daného testu a rekurzívne sa vnor do každého 
				nového vrcholu s novou množinou príkladov, ktorá obsahuje už len príklady, ktorých výsledok testu momentálneho vrcholu je v príslušnej prechodovej hrane.
		\end{enumerate}

		Ostáva už len určiť, ktorý atribút v momentálnej množine dátových príkladov je najinformatívnejší. Nech to je atribút, výberom ktorého dosiahneme najvyšší 
		\emph{informačný zisk (information gain)} \cite{aima:2003}, čo je rozdiel entropie množiny príkladov pred a po rozdelení na podmnožiny podľa vybraného atribútu.
		
		Entropiu množiny trénovacích príkladov $S$ vypočítame ako
		\begin{displaymath}
			E(S) = \sum_{j = 1}^{C}-P(c_j)\log_2 P(c_j)
		\end{displaymath}
		kde $P(c_j)$ reprezentuje pravdepodobnosť dátovej triedy $c_j$ medzi dátovými príkladmi množiny $S$ a $C$ je celkový počet dátových tried
		v danej množine.

		Informačný zisk potom vypočítame ako rozdiel entropie množiny príkladov $S$ a sumy entropií podmnožín, ktoré vzniknú rozdelením $S$ podľa vybraného
		atribútu $Attr$
		\begin{displaymath}
			I(Attr, S) = E(S) - \sum_{j = 1}^{A}P(S_j)E(S_j)
		\end{displaymath}
		kde $A$ je celkový počet možných hodnôt atribútu $Attr$, $S_j$ reprezentuje $j$-tu novú podmnožinu po rozdelení $S$ podľa hodnôt atribútu $Attr$, $P(S_j)$
		je pravdepodobnosť výskytu príkladov podmnožiny $S_j$ v množine $S$.

		Nevýhodou algoritmu je použitie \emph{greedy} princípu pri výbere ďalšieho atribútu, teda myslíme si, že najlepší atribút, podľa ktorého máme strom 
		teraz rozvetviť je ten, ktorý má \emph{najväčší} informačný prínos, teda najviac usporiada výsledné podmnožiny príkladov. Takýto prístup nezaručuje
		optimálne riešenie, môže uviaznuť v lokálnom extréme.

		Schopnosti rozhodovacích stromov je možné zlepšiť použitím zložitejších metód učenia pomenovaných \emph{ensemble learning} \cite{aima:2003}. Tieto metódy učenia 
		uvažujú viac rozhodovacích stromov pre jeden problém, ktoré sa od seba odlišujú. 

		V prípade prístupu \emph{bagging} rozdelíme trénovaciu množinu na podmnožiny, na ktorých vytvoríme osobitné stromy. Tieto potom hlasujú o celkovej 
		výstupnej hodnote klasifikátora väčšinovým hlasom. 
		
		Iným prístupom tejto kategórie je \emph{boosting}, pri ktorom zavedieme váhy pre jednotlivé trénovacie príklady s cieľom zdôrazniť ich dôležitosť pri trénovaní
		jednotlivých stromov. Postupne sa trénujú nové rozhodovacie stromy, pričom trénovacie príklady, ktoré predošlý strom klasifikoval nesprávne dostanú 
		vyššiu prioritu pri trénovaní nového stromu. Nakoniec natrénujeme daný počet stromov, ktoré opäť hlasujú o výstupnej celkovej hodnote klasifikátora
		princípom váhovanej väčšiny (úspešnejší strom má silnejší hlas) \cite{aima:2003}.
		


